package com.lhcai.lc.other;

/**
 * @author lhcstart
 * @create 2023-02-25 20:36
 */


import java.util.Arrays;

/**
 * 计数质数
 * 给定整数 n ，返回所有小于非负整数 n 的质数的数量
 */
public class lc204 {

    public int countPrimes(int n) {

        int[] isPrime = new int[n];
        Arrays.fill(isPrime, 1);

        int count = 0;
        for (int i = 2; i < n; i++) {
            if (isPrime[i] == 1) {
                count++;
                if (i * i < n) {
                    for (int j = i * i; j < n; j += i) {
                        isPrime[j] = 0;
                    }
                }

            }
        }
        return count;
    }
}
